﻿#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

//【题目】力扣560.和为KK的子数组
//【难度】中等
//【提交】https://leetcode.cn/problems/subarray-sum-equals-k/submissions/669073915/
//【标签】数组；哈希表；前缀和

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        cnt[0] = 1;
        int prev = 0;
        int ans = 0;
        for (int x : nums)
        {
            prev += x;
            if (cnt.count(prev - k))
            {
                ans += cnt[prev - k];
            }
            cnt[prev]++;
        }
        return ans;
    }
};

/*
学习总结：
通过计算前缀和，将问题转化为“寻找两个前缀和之差等于k”的统计问题。
哈希表用于记录每个前缀和出现的次数，这样可以在O(1)时间内查询到能与当前前缀和组成差值为k的历史前缀和个数。
这种方法将时间复杂度从暴力解的O(n²)降到了O(n)，空间复杂度为O(n)。
需要注意的细节是初始化cnt[0]=1，表示前缀和为0的情况（即从数组开头开始的子数组）。
*/